package arrays;

import java.util.Arrays;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * 示例 1:
 *
 * 输入: coins = [1, 2, 5], amount = 11
 * 输出: 3
 * 解释: 11 = 5 + 5 + 1
 * 示例 2:
 *
 * 输入: coins = [2], amount = 3
 * 输出: -1
 * 说明:
 * 你可以认为每种硬币的数量是无限的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class CoinChange {
    /* backtack very slow
    int minCount = Integer.MAX_VALUE;

    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length == 0){
            return -1;
        }
        Arrays.sort(coins);

        if(changes(coins, amount, 0, 0)){
            return minCount;
        } else {
            return -1;
        }
    }

    private boolean changes(int[] coins, int amount, int count, int index){
        if(index == coins.length){
            if(amount == 0){
                if(count < minCount) {
                    minCount = count;
                }
                return true;
            }
            return false;
        }
        boolean hasChange = false;
        for(int i = index; i <= coins.length - 1; i ++) {
            int curCount = 0;
            while(amount >= coins[i] * curCount){
                int curAmount = amount;
                if(curCount + count >= minCount){
                    break;
                }
                curAmount -= coins[i] * curCount;

                if(changes(coins, curAmount, curCount + count, index + 1)){
                    hasChange = true;
                }
                curCount ++;
            }

        }
        return hasChange;
    }

     */

    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length < 1){
            return -1;
        }
        int[] results = new int[amount + 1];
        return changes(coins, amount, results);
    }

    private int changes(int[] coins, int amount, int[] results){
        if(amount < 0){
            return -1;
        }
        if(amount == 0){
            return 0;
        }
        if(results[amount] != 0){
            return results[amount];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < coins.length; i ++){
            int v = amount - coins[i];
            int count = changes(coins, v, results);
            if(count != -1) {
                if (count + 1 < min) {
                    min = count + 1;
                }
            }
        }
        if(min == Integer.MAX_VALUE){
            results[amount] = -1;
        } else {
            results[amount] = min;
        }
        return results[amount];
    }

    public static void main(String[] args){
        System.out.println((new CoinChange()).coinChange(new int[]{227,99,328,299,42,322}, 9847));
    }
}
